// Copyright 2021 The Lynx Authors. All rights reserved.
// Licensed under the Apache License Version 2.0 that can be found in the
// LICENSE file in the root directory of this source tree.

#ifndef CORE_RENDERER_UTILS_DIFF_ALGORITHM_H_
#define CORE_RENDERER_UTILS_DIFF_ALGORITHM_H_

#include <algorithm>
#include <functional>
#include <iterator>
#include <unordered_map>
#include <unordered_set>
#include <utility>

#include "base/include/vector.h"

#ifndef CHECK_RESULT
#define CHECK_RESULT __attribute__((warn_unused_result))
#endif

namespace lynx {
namespace tasm {
// issue: #1829
// Myers Diff Algorithm For Components in List
// For detail of the implementation of the Iterative MyersDiff
namespace myers_diff {

using IndexType = int32_t;
constexpr IndexType kInvalidIndex = INT32_MIN;

using IndexVector = base::InlineVector<IndexType, 8>;

// Operations types generated by the algorithm
enum class Operations : int32_t {
  NOOP = -1,
  REMOVE = 0,
  INSERT = 1,
  UPDATE = 2,
  MOVE = 3,
};

namespace detail {
// Point resembles a point on the edit map
//
//       Point{2, 1}
//       ^
//       |
//    A B|C D
//   +-----+-+
//  A|\| | | |
//   +---X---+
//  C| | |\| |
//   +-------+
//  D| | | |\|
//   +-+-+---+

struct Point {
  IndexType x_{0};
  IndexType y_{0};

  friend bool operator==(const Point& lhs, const Point& rhs) {
    return lhs.x_ == rhs.x_ && lhs.y_ == rhs.y_;
  }

  friend bool operator!=(const Point& lhs, const Point& rhs) {
    return !(lhs == rhs);
  }

  friend bool operator<(const Point& lhs, const Point& rhs) {
    return lhs.x_ == rhs.x_ ? lhs.y_ < rhs.y_ : lhs.x_ < rhs.x_;
  }
};

using PointVector = base::InlineVector<Point, 16>;

// Operations with the index it will be applied on
// Generated by GenerateOperation(Point lhs, Point rhs, Compare compare) from
// Point operation_ could only be
struct DiffOperation {
  Operations operation_{Operations::NOOP};
  Point point_{-1, -1};
};

// Box is the area specified by two points
//   Box{Point{0,0}, Point{2, 2}}
//   ^
//   |
//   +A B C D
//   X++++---+
//  A+\| + | |
//   +---+---+
//  C+ | +\| |
//   ++++X---+
//  D| | | |\|
//   +-------+
//

struct Box {
  Point top_left_{};
  Point bottom_right_{};

  IndexType Width() const { return bottom_right_.x_ - top_left_.x_; }

  IndexType Height() const { return bottom_right_.y_ - top_left_.y_; }

  IndexType Size() const { return Width() + Height(); }

  IndexType Delta() const { return Width() - Height(); }

  IndexType Top() const { return top_left_.y_; }

  IndexType Left() const { return top_left_.x_; }

  IndexType Bottom() const { return bottom_right_.y_; }

  IndexType Right() const { return bottom_right_.x_; }
};

// pair.first indicates whether the result exists or not
// if pair.first is 'true', then pair.second contains the result
using MyersInnerResultType = std::pair<bool, Box>;
struct MidPointValueType {
  IndexType max_;
  Box box_;
};
using MyersMidPointCacheMap = std::unordered_map<IndexType, MidPointValueType>;

// Iterative MyersDiff Algorithm that strats from the upper left corner and
// moves down/right. detail in online Document
template <typename Compare>
MyersInnerResultType MyersForward(Box box, IndexType d,
                                  MyersMidPointCacheMap& forward_max_x,
                                  MyersMidPointCacheMap& backward_max_x,
                                  Compare& compare) {
  for (IndexType k = -d; k <= d; k += 2) {
    IndexType c = k - box.Delta();
    IndexType x = 0;
    IndexType px = 0;

    if (k == -d ||
        (k != d && forward_max_x[k - 1].max_ < forward_max_x[k + 1].max_)) {
      px = x = forward_max_x[k + 1].max_;
    } else {
      px = forward_max_x[k - 1].max_;
      x = px + 1;
    }

    IndexType y = box.Top() + (x - box.Left()) - k;
    IndexType py = 0;
    if (d == 0 || x != px) {
      py = y;
    } else {
      py = y - 1;
    }

    while (x < box.Right() && y < box.Bottom() && compare(x, y)) {
      ++x;
      ++y;
    }

    forward_max_x[k] = {x, Box{{px, py}, {x, y}}};

    if (box.Delta() % 2 != 0 && (c >= -(d - 1) && c <= (d - 1)) &&
        (y >= backward_max_x[c].max_)) {
      return MyersInnerResultType{true, {{px, py}, {x, y}}};
    }
  }

  return MyersInnerResultType{false, {}};
}

// Iterative MyersDiff Algorithm that strats from the bottom right corner and
// moves up/left. detail in online Document
template <typename Compare>
MyersInnerResultType MyersBackward(Box box, IndexType d,
                                   MyersMidPointCacheMap& forward_max_x,
                                   MyersMidPointCacheMap& backward_max_x,
                                   Compare& compare) {
  for (IndexType c = -d; c <= d; c += 2) {
    IndexType k = c + box.Delta();
    IndexType py = 0;
    IndexType y = 0;

    if (c == -d ||
        (c != d && backward_max_x[c - 1].max_ > backward_max_x[c + 1].max_)) {
      py = y = backward_max_x[c + 1].max_;
    } else {
      py = backward_max_x[c - 1].max_;
      y = py - 1;
    }

    IndexType x = box.Left() + (y - box.Top()) + k;
    IndexType px = 0;
    if (d == 0 || y != py) {
      px = x;
    } else {
      px = x + 1;
    }

    while (x > box.Left() && y > box.Top() && compare(x - 1, y - 1)) {
      --x;
      --y;
    }

    backward_max_x[c] = {y, Box{{x, y}, {px, py}}};

    if (box.Delta() % 2 == 0 && (k >= -d && k <= d) &&
        x <= forward_max_x[k].max_) {
      // find the snake that intercept with this snake
      // we prefer the other snake if it has greater x.
      const auto& intercept_snake = forward_max_x[k];
      if (intercept_snake.box_.bottom_right_.x_ > px) {
        return MyersInnerResultType{true, intercept_snake.box_};
      }
      return MyersInnerResultType{true, {{x, y}, {px, py}}};
    }
  }
  return MyersInnerResultType{false, {}};
}

// Do MyersForward from the upper left corner of box and MyersBackward
// simultaneously until they come across each other. RETURN the very Box where
// they came across each other.
template <typename Compare>
MyersInnerResultType MyersMidPoint(Box box, Compare& compare) {
  if (box.Size() == 0) {
    return std::make_pair(false, Box{});
  }

  auto max = (box.Size() + 1) / 2;
  // set the start k and c to be 1.
  // MyersForward will enter the searching at (box.top_left_.x_,
  // box.top_left_.y_ - 1) MyersBackward will enter the searching at
  // (box.bottom_right_.x_, box.bottom_right_.y_ + 1)
  auto forward_max_x_start_box = Box{box.top_left_, box.top_left_};
  auto backward_max_x_start_box = Box{box.bottom_right_, box.bottom_right_};
  auto forward_max_x = MyersMidPointCacheMap{
      {1, MidPointValueType{box.top_left_.x_, forward_max_x_start_box}}};
  auto backward_max_x = MyersMidPointCacheMap{
      {1, MidPointValueType{box.bottom_right_.y_, backward_max_x_start_box}}};

  for (IndexType d{}; d <= max; ++d) {
    auto res = MyersForward(box, d, forward_max_x, backward_max_x, compare);
    if (res.first) {
      return res;
    }
    res = MyersBackward(box, d, forward_max_x, backward_max_x, compare);
    if (res.first) {
      return res;
    }
  }

  return MyersInnerResultType{false, Box{}};
}

template <typename Compare>
Box FindPathAlongCornerForwards(Box box, Compare& compare,
                                PointVector& result) {
  auto start = box.top_left_;
  auto end = box.bottom_right_;
  // try to move along the corner as much as possible
  while (start.x_ < end.x_ && start.y_ < end.y_ &&
         compare(start.x_, start.y_)) {
    ++start.x_;
    ++start.y_;
    result.push_back(start);
  }
  return {start, end};
}

template <typename Compare>
Box FindPathAlongCornerBackward(Box box, Compare& compare,
                                PointVector& result) {
  auto start = box.bottom_right_;
  auto end = box.top_left_;

  while (start.x_ > end.x_ && start.y_ > end.y_ &&
         compare(start.x_ - 1, start.y_ - 1)) {
    --start.x_;
    --start.y_;
    result.emplace_back(start);
  }

  std::reverse(result.begin(), result.end());
  return {end, start};
}

template <typename Compare1, typename Compare2>
void FindPath(Point top_left, Point bottom_right, Compare1& compare1,
              Compare2& compare2, PointVector& result) {
  // Myers Diff cuts the whole edit map into three boxs, and plays __divide and
  // conquer__ on the upper left one and the bottom right one.
  Box box{top_left, bottom_right};
  box = FindPathAlongCornerForwards(box, compare2, result);
  PointVector backward_path;
  box = FindPathAlongCornerBackward(box, compare2, backward_path);
  auto snake = MyersMidPoint(box, compare1);
  if (!snake.first) {
    // the box is too small to find a middle snake, no need to do recursively.
    return;
  }
  // __divide and conquer__ on the upper left Box
  FindPath(box.top_left_, snake.second.top_left_, compare1, compare2, result);
  // record the result with an inorder-traversal manner
  result.push_back(snake.second.bottom_right_);
  // __divide and conquer__ on the bottom right Box
  FindPath(snake.second.bottom_right_, box.bottom_right_, compare1, compare2,
           result);
  std::copy(backward_path.begin(), backward_path.end(),
            std::back_inserter(result));
}

// Generate operation with two points
// two points together resemble a __SNAKE__
// a __SNAKE__ contains one right move or down move with arbitrary number of
// corner moves

// Remove duplicates indices from removee if removee and remover both have them.
// REQUIRES: remover is sorted.
template <typename Container>
void RemoveDuplicates(Container& removee, const Container& remover) {
  removee.erase(std::remove_if(removee.begin(), removee.end(),
                               [&remover](const auto& i) {
                                 return std::binary_search(remover.begin(),
                                                           remover.end(), i);
                               }),
                removee.end());
}

}  // namespace detail

// DiffResult
//
// NOOP operation only be used in inner state, thus no vector contains it.
// REMOVE, INSERT, UPDATE operate on only one index
// REMOVE operates on the index __before__ the list is modified
// INSERT operates on the index __after__  the list is modified
// UPDATE operates on the index __before__ or __after__ the list is modified,
// becase indices that are updated does not change their indices after or before
// the modification MOVE operates on two indices, move_from is the index
// __before__ the lsit is modified, move_to is the index
// __after__ the list is modified.

struct DiffResultBase {
 public:
  IndexVector insertions_{};
  IndexVector removals_{};

  DiffResultBase() = default;

  // Build the DiffResult from the Path Generated by MyersDiff
  template <typename Compare>
  explicit DiffResultBase(const detail::PointVector& path, Compare compare) {
    for (auto i = size_t{1}; i < path.size(); ++i) {
      GenerateOperation(path[i - 1], path[i], compare);
    }
  }

 protected:
  detail::Point GenerateInsertionDeletionOperation(detail::Point lhs,
                                                   detail::Point rhs) {
    //  There are two kind of snakes:
    //  1. a down or right move followed by some corner moves
    //  2. some corner moves followed by a down or right move
    //
    //    X+--+-+  XXX---+
    //    +X+ | |  | |X| |
    //    ++X+--+  +---X-+
    //    | +X+ +  | | |X|
    //    +--+XXX  +-+---X
    auto dx = rhs.x_ - lhs.x_;
    auto dy = rhs.y_ - lhs.y_;

    if (dy < dx) {
      // dy < dx indicates that there should be right move
      removals_.push_back(lhs.x_);
      // move lhs.x_ one step right
      ++lhs.x_;
    } else if (dx < dy) {
      // otherwise a down move
      insertions_.push_back(lhs.y_);
      // move lhs.y_ one step down
      ++lhs.y_;
    }

    return lhs;
  }

 private:
  template <typename Compare>
  detail::Point SkipSameAlongCorners(detail::Point lhs, detail::Point rhs,
                                     Compare& compare) {
    while (lhs.x_ < rhs.x_ && lhs.y_ < rhs.y_) {
      if (!compare(lhs.x_, lhs.y_)) {
        return lhs;
      }
      ++lhs.x_;
      ++lhs.y_;
    }
    return lhs;
  }

  template <typename Compare>
  void GenerateOperation(detail::Point lhs, detail::Point rhs,
                         Compare& compare) {
    // try to move along the corner to find some updates
    lhs = SkipSameAlongCorners(lhs, rhs, compare);
    GenerateInsertionDeletionOperation(lhs, rhs);
  }
};

struct DiffResult : public DiffResultBase {
 public:
  IndexVector update_from_{};
  IndexVector update_to_{};
  IndexVector move_from_{};
  IndexVector move_to_{};

  struct EnableMoveDetection : std::true_type {};

  DiffResult() = default;

  // Build the DiffResult from the Path Generated by MyersDiff, then detects and
  // generates __UPDATE__s
  // Compare1 testing whether two nodes are the same
  // Compare2 testing whether two nodes are of the same __KIND__
  template <typename Compare1, typename Compare2>
  DiffResult(const detail::PointVector& path, Compare1& compare1,
             Compare2& compare2) {
    for (auto i = size_t{1}; i < path.size(); ++i) {
      GenerateOperation(path[i - 1], path[i], compare1, compare2);
    }
  }

  // Build the DiffResult from the Path Generated by MyersDiff, then detects and
  // generates __UPDATE__s and __MOVE__s
  // Compare1 testing whether two nodes are the same
  // Compare2 testing whether two nodes are of the same __KIND__
  template <typename Compare1, typename Compare2>
  DiffResult(const detail::PointVector& path, Compare1& compare1,
             Compare2& compare2, EnableMoveDetection)
      : DiffResult{path, compare1, compare2} {
    DetectMoves(compare2);
  }

  void Clear() {
    insertions_.clear();
    removals_.clear();
    update_from_.clear();
    update_to_.clear();
    move_from_.clear();
    move_to_.clear();
  }

  // Test if the diff result is empty or not
  bool Empty() const {
    return insertions_.empty() && removals_.empty() && update_from_.empty() &&
           update_to_.empty() && move_from_.empty() && move_to_.empty();
  }

 private:
  template <typename Compare1, typename Compare2>
  detail::Point GenerateUpdateOperationAlongCorners(detail::Point lhs,
                                                    detail::Point rhs,
                                                    Compare1& compare1,
                                                    Compare2& compare2) {
    while (lhs.x_ < rhs.x_ && lhs.y_ < rhs.y_) {
      auto sameComponent = compare1(lhs.x_, lhs.y_);
      auto sameData = compare2(lhs.x_, lhs.y_);
      if (!sameComponent) {
        return lhs;
      }
      if (!sameData) {
        update_from_.push_back(lhs.x_);
        update_to_.push_back(lhs.y_);
      }
      ++lhs.x_;
      ++lhs.y_;
    }
    return lhs;
  }

  template <typename Compare1, typename Compare2>
  void GenerateOperation(detail::Point lhs, detail::Point rhs,
                         Compare1& compare1, Compare2& compare2) {
    // try to move along the corner to find some updates
    lhs = GenerateUpdateOperationAlongCorners(lhs, rhs, compare1, compare2);
    lhs = GenerateInsertionDeletionOperation(lhs, rhs);
    GenerateUpdateOperationAlongCorners(lhs, rhs, compare1, compare2);
  }
  // Detect __MOVE__s from removals and insertions
  // __MOVE__ indicates the same node removed and inserted at different indices
  // for example: (remove, 0, 'A') then (insert, 10, 'A') could be converted
  // into a move operation: (move, 0, 10, 'A').
  template <typename Compare>
  void DetectMoves(Compare& compare) {
    auto move_to_used = std::unordered_set<int>{};
    for (auto i : removals_) {
      for (auto j : insertions_) {
        if (compare(i, j) && !move_to_used.count(j)) {
          move_from_.push_back(i);
          move_to_.push_back(j);
          move_to_used.insert(j);
        }
      }
    }
    IndexVector move_to_sorted = move_to_;
    std::sort(move_to_sorted.begin(), move_to_sorted.end());
    detail::RemoveDuplicates(insertions_, move_to_sorted);
    detail::RemoveDuplicates(removals_, move_from_);
  }
};

namespace detail {

// Generate the operation path for MyersDiff
template <typename RandomAccessIt1, typename RandomAccessIt2, typename Compare1,
          typename Compare2,
          typename DifferenceType =
              typename std::iterator_traits<RandomAccessIt1>::difference_type>
CHECK_RESULT detail::PointVector MyersDiffPath(
    RandomAccessIt1 first1, RandomAccessIt1 last1, RandomAccessIt2 first2,
    RandomAccessIt2 last2, Compare1& compare1, Compare2& compare2) {
  DifferenceType size1{last1 - first1};
  DifferenceType size2{last2 - first2};

  auto top_left = detail::Point{0, 0};
  auto bottom_right = detail::Point{static_cast<IndexType>(size1),
                                    static_cast<IndexType>(size2)};

  auto res = detail::PointVector{top_left};
  FindPath(top_left, bottom_right, compare1, compare2, res);
  res.push_back(bottom_right);

  return res;
}

using IndicesPair = std::pair<IndexType, IndexType>;

// Szudzik Pairing Function
// http://szudzik.com/ElegantPairing.pdf
struct IndicesPairHash {
  std::size_t operator()(const IndicesPair& pair) const {
    const auto x = pair.first;
    const auto y = pair.second;
    const auto max_x_y = std::max(x, y);
    if (x == max_x_y) {
      return x * x + x + y;
    } else {
      return y * y + x;
    }
  }
};

template <typename BinaryPredicate>
struct CachedComparator {
  BinaryPredicate pred_;
  std::unordered_map<IndicesPair, bool, IndicesPairHash> cached_result_ = {};

  explicit CachedComparator(BinaryPredicate pred) : pred_{pred} {}

  bool operator()(IndexType lhs, IndexType rhs) {
    const auto indices_pair = IndicesPair{lhs, rhs};
    auto cache = cached_result_.find(indices_pair);
    if (cache != cached_result_.end()) {
      return cache->second;
    }
    // cache missed
    const bool result = pred_(lhs, rhs);
    cached_result_[indices_pair] = result;
    return result;
  }
};

template <typename RandomAccessIt, typename BinaryPredicate>
auto GenerateCachedComparator(RandomAccessIt first1, RandomAccessIt first2,
                              BinaryPredicate pred) {
  auto compare = [pred, first1, first2](IndexType i, IndexType j) {
    return pred(*(first1 + i), *(first2 + j));
  };
  return CachedComparator<decltype(compare)>{compare};
}

}  // namespace detail

// The MyersDiff Algorithm With Update and Move Dectection
// range: [first1, last1) the original range
// range: [first2, last2) the range you want to transform to
// pred1: compare if two nodes in ranges [first1, last1) and
// [first2, last2) are of the same __KIND__, nodes with same __KIND__ could be
// __UPDATE__'ed instead of removed then inserted.
// pred2: compare if two nodes in ranges [first1, last1) and [first2, last2) are
// the __SAME__
template <typename RandomAccessIt1, typename RandomAccessIt2,
          typename BinaryPredicate1 = std::equal_to<
              typename std::iterator_traits<RandomAccessIt1>::value_type>,
          typename BinaryPredicate2 = std::equal_to<
              typename std::iterator_traits<RandomAccessIt1>::value_type>>
__attribute__((warn_unused_result)) DiffResult MyersDiff(
    bool enable_move_detection, RandomAccessIt1 first1, RandomAccessIt1 last1,
    RandomAccessIt2 first2, RandomAccessIt2 last2,
    BinaryPredicate1 pred1 = BinaryPredicate1{},
    BinaryPredicate2 pred2 = BinaryPredicate2{}) {
  auto compare1 = [pred1, first1, first2](IndexType i, IndexType j) {
    return pred1(*(first1 + i), *(first2 + j));
  };

  auto compare2 = [pred2, first1, first2](IndexType i, IndexType j) {
    return pred2(*(first1 + i), *(first2 + j));
  };

  auto cached_compare1 = detail::CachedComparator<decltype(compare1)>{compare1};
  auto cached_compare2 = detail::CachedComparator<decltype(compare2)>{compare2};
  auto path = detail::MyersDiffPath(first1, last1, first2, last2,
                                    cached_compare1, cached_compare2);
  if (enable_move_detection) {
    return DiffResult{path, cached_compare1, cached_compare2,
                      DiffResult::EnableMoveDetection{}};
  }
  return DiffResult{
      path,
      cached_compare1,
      cached_compare2,
  };
}

// The MyersDiff Algorithm Without Update
// range: [first1, last1) the original range
// range: [first2, last2) the range you want to transform to
// pred1: compare if two nodes in ranges [first1, last1) and [first2, last2) are
// the __SAME__
template <typename RandomAccessIt1, typename RandomAccessIt2,
          typename BinaryPredicate1 = std::equal_to<
              typename std::iterator_traits<RandomAccessIt1>::value_type>>
CHECK_RESULT DiffResultBase MyersDiffWithoutUpdate(
    RandomAccessIt1 first1, RandomAccessIt1 last1, RandomAccessIt2 first2,
    RandomAccessIt2 last2, BinaryPredicate1 pred1 = BinaryPredicate1{}) {
  auto cached_compare1 =
      detail::GenerateCachedComparator(first1, first2, pred1);
  auto path = detail::MyersDiffPath(first1, last1, first2, last2,
                                    cached_compare1, cached_compare1);
  return DiffResultBase{path, cached_compare1};
}
}  // namespace myers_diff
}  // namespace tasm
}  // namespace lynx

#endif  // CORE_RENDERER_UTILS_DIFF_ALGORITHM_H_
